#define _CRT_SECURE_NO_WARNINGS

int singleNonDuplicate(int* nums, int numsSize) {
    // int ret = 0;
    // for (int i = 0; i < numsSize; i++)
    //     ret ^= nums[i];

    // return ret;

    int left = 0;
    int right = numsSize - 1;
    while (left < right)
    {
        int mid = (right - left) / 2 + left;
        if (mid % 2 == 0)
        {
            if (nums[mid] == nums[mid + 1])
                left = mid + 1;
            else
                right = mid;
        }
        else
        {
            if (nums[mid - 1] == nums[mid])
                left = mid + 1;
            else
                right = mid;
        }
    }

    return nums[left];
}